# -*- coding: utf-8 -*-
# @File    : test.py
# @Date    :  2024-11-18 16:54
# @Author  : zoey1
from datetime import datetime
from typing import List


class Solution:
    """
    面试经典150题-[数组/字符串]-169. 多数元素
    给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

    你可以假设数组是非空的，并且给定的数组总是存在多数元素。

    解题思路：
    注意：
        在本文中，“数组中出现次数超过一半的数字” 被称为 “众数” 。
        需要注意的是，数学中众数的定义为 “数组中出现次数最多的数字” ，与本文定义不同
    按本题的众数概念，所以可以使用“摩尔投票”方法推算
    摩尔投票：
        设输入数组 nums 的众数为 x ，数组长度为 n 。
        推论一： 若记 众数 的票数为 +1 ，非众数 的票数为 −1 ，则一定有所有数字的 票数和 >0 。
        推论二： 若数组的前 a 个数字的 票数和 =0 ，则 数组剩余 (n−a) 个数字的 票数和一定仍 >0 ，即后 (n−a) 个数字的 众数仍为 x 。
    实现方法：
        遍历每个元素，从第一个元素开始，假设是众数x，然后去算投票和；如果投票和==0，则众数在剩余的元素还是存在，更新众数的取值，直到最后
    """

    def majorityElement(self, nums: List[int]) -> int:
        x = nums[0]
        vote_sum = 1
        for i in range(1, nums.__len__()):
            if vote_sum == 0:
                x = nums[i]
            if nums[i] == x:
                vote_sum += 1
            else:
                vote_sum -= 1

        print('存在最多的元素：', x)
        return x

    def majorityElement_jianjie(self, nums: List[int]) -> int:
        """上面写法的，再简洁一下"""
        vote_sum = 0
        for i in range(nums.__len__()):
            if vote_sum == 0:
                x = nums[i]
            if nums[i] == x:
                vote_sum += 1
            else:
                vote_sum -= 1

        print('存在最多的元素：', x)
        return x

    def majorityElement_review_20250729(self, nums: List[int]) -> int:
        """
        解题思路：
        题目关键：多数元素是指出现次数>n/2的元素
        ！！！摩尔投票算法：
        多数元素赋值+1，非多数元素赋值-1；
        并且有个特性：从0开始，从左到右，依次求和，排除前N个和为0的子元素，多数元素依然在后续的元素中存在
        用这个思路解题
        """
        val = float('-inf')
        sum_result = 0
        for x in nums:
            if sum_result == 0:
                val = x
            # else:
            # 这里出了个bug，不应该写在上面的if-else里面，因为当取得x的时候，也需要+1赋一下值
            if x == val:
                sum_result += 1
            else:
                sum_result -= 1
        print('val:', val)
        return val

    def majorityElement_review_20250729_2(self, nums: List[int]) -> int:
        """
        解题思路：
        题目关键：多数元素是指出现次数>n/2的元素
        用冒泡排序法排序，众数一定是下标为n/2的元素
        注意：能解题，但是时间复杂度太高
        """
        n = len(nums)
        # 升序
        for i in range(n):
            for j in range(i, n):
                if nums[i] > nums[j]:
                    temp = nums[j]
                    nums[j] = nums[i]
                    nums[i] = temp
        val = nums[int(n / 2)]
        print('val:', val)
        return val

    def majorityElement_review_20250731_3(self, nums: List[int]) -> int:
        """
        解题思路：
        题目关键：多数元素是指出现次数>n/2的元素
        摩尔投票法
        冒泡排序法众数一定在中间下标的元素【时间复杂度太高，不适用】
        """

    def majorityElement_review_20250803(self, nums: List[int]) -> int:
        """
        解题思路：找大于n/2的众数【重要，有这个前提，才能使用摩尔投票法】
        摩尔投票法，是众数+1，不是众数-1，累加和=0的情况下，众数还是会出现在右边没有进行累加的子元素部分
        代码实现，从第一个元素开始，假设是众数x
        """
        count = 0
        x = nums[0]
        for ele in nums:
            if count == 0:
                x = ele
            if ele == x:
                count += 1
            else:
                count -= 1
        print('x:', x)
        return x


if __name__ == '__main__':
    # nums = [3, 2, 3]
    nums = [2, 2, 1, 1, 1, 2, 2]
    s = Solution()
    # e = s.majorityElement_jianjie(nums)
    # e = s.majorityElement_review_20250729(nums)
    # e = s.majorityElement_review_20250729_2(nums)
    e = s.majorityElement_review_20250803(nums)
